"""
例16 移动石子
1．问题描述
在x轴上分布着n个石子，用arr数组表示它们的位置。把这些石子移
动到1，3，5，7，2n-1或者2，4，6，8，2n。也就是说，这些石子移动
到从1开始连续的奇数位，或从2开始连续的偶数位上。返回最少的移动
次数。每次只可以移动1个石子，只能把石子往左移动1个单位或往右移
动1个单位。同一个位置不能同时有2个石子。
2．问题示例
[5，4，1]，只需要把4移动1步到3，所以输出是1。arr=[1，6，7，
8，9]，最优的移动方案为把1移动到2，把6移动到4，把7移动到6，把9
移动到10，所以输出是5。
"""


def moving_stones(arr):
    arr = sorted(arr)
    even = 0
    odd = 0
    for i in range(0, len(arr)):
        odd += abs(arr[i] - (2 * i + 1))
        even += abs(arr[i] - (2 * i + 2))
    if odd < even:
        return odd
    return even


if __name__ == '__main__':
    arr = [1, 6, 7, 8, 9]
    print(moving_stones(arr))
